/********************************************
 *        Fonctions de triangulation        *
 *            	  LexBFS.h                  *
 *                                          *
 *     Grivolet Alenda Bourgeois Ciabaud    *
 ********************************************/

#ifndef __LEXBFS_H__
#define __LEXBFS_H__

#include "structures.h"

/**********************/
/***                ***/
/*** NOUVEAUX TYPES ***/
/***                ***/
/**********************/

/** Type Etiquette. Sert à la linéarisation des algorithmes */
typedef struct
{
      int taille;                 /** < Nombre d'étiquettes (nombre de sommets du graphe à traiter). */
      int *etiquette;             /** < indique, pour chaque sommet, la valeur de son étiquette. */
      DMaillon *sommets;          /** < contient, pour chaque sommet, le DMaillon le réprésentant. */
      DMaillon *val_etiquette;    /** < contient, pour chaque étiquette, le DMaillon la représentant. */
      DListe *liste_etiquette;    /** < contient, pour chaque étiquette, la liste des sommets de cette étiquette. */
      DListe max_etiquette;       /** < indique la première étiquette non vide. */
} Etiquette;

/* structure de file */
typedef struct _File{

	int Val;

	struct _File *Suivant;

} File;

/* Recherche si un Graphe est triangulé */
int estTriangule( Graphe G );

/* Recherche un schéma d'élimination parfait dans G a partir de S */
int existeSchema( Graphe G, int S );

/* Recherche si S est un sommet simplicial dans G */
int estSimplicial( Graphe G, int S );

/* Retourne le Graphe Induit de G par ensemble
 *
 * ensemble : tableau de sommet avec 
 * ensemble[i] = 1 si le sommet i apartient a l'ensemble 
 * ensemble[i] = 0 sinon.
 * et Longueur(ensemble) = G.nbSommets
 */
Graphe* grapheInduit( Graphe G, int *ensemble );

/* Recherche si G est complet */
int estComplet( Graphe G );

/* Numerote G selon le schema d élimination simplicial ssi G est triangulé */
Numerotation* LexBFS( Graphe G );

/* Verifie si la numerotation N represente un graphe triangule */
int verifLexBFS( Numerotation N, Graphe G );

/* Numerote G selon le schema d Ã©limination simplicial ssi G est triangulÃ© et fait la liste des cliques maximales */
Numerotation* LexBFS_Cliques( Graphe G, LDL *EC );

/**
 * @author ALENDA Régis
 * @brief Alloue la mémoire et initialise un type Etiquette.
 * Alloue la mémoire et effectue l'initialisation d'un type étiquette.
 * Au début, toutes les étiquettes sont vides.
 * @param E Pointeur sur l'Etiquette à traiter.
 * @param taille Nombre d'étiquettes (= nombre de sommets du graphe).
 */
void initEtiquette( Etiquette *E, int taille );

/**
 * @author ALENDA Régis
 * @brief Met tous les sommets à l'étiquette zéro.
 * Met tous les sommets dans l'étiquette zéro.
 * @param E Un pointeur sur l'étiquette à traiter.
 */
void mettreEtiquetteAZero( Etiquette *E );

/**
 * @author ALENDA Régis
 * @brief Renvoie un sommet d'étiquette maximum.
 * Renvoie un sommet d'étiquette maximum, et supprime ce sommet de l'Etiquette. Renvoie -1 si toutes les étiquettes sont vides.
 * @param E Pointeur vers l'Etiquette considérée.
 * @return Un sommet d'étiquette maximum.
 */
int getMaxEtiquette( Etiquette *E );

/**
 * @author ALENDA Régis
 * @brief Incrémente l'étiquette d'un sommet.
 * Incrémente l'étiquette d'un sommet.
 * @attention Le sommet est supposé être encore actif dans l'Etiquette (c-a-d il appartient bien à une étiquette).
 * @attention Aucun test n'est effectué pour vérifier que l'on est bien dans les limites des valeurs des étiquettes (l'étiquette d'un sommet ne peux être superieure au nombre de sommets du graphe).
 * @param s Un sommet.
 * @param E Un pointeur vers une Etiquette.
 */
void incrementerEtiquette( int s, Etiquette *E );

/**
 *  * @author ALENDA Régis
 *   * @brief Libère la mémoire d'une étiquette.
 *    * Libère la mémoire allouée pour une Etiquette par initEtiquette().
 *     * @param E Un pointeur sur l'étiquette à traiter.
 *      */
void freeEtiquette( Etiquette *E );

#endif

